Leetcode Day 1

@2025-04-28，今天开始开新坑，刷刷Leetcode，虽然我是学数学的，但是代码太菜不太好找饭吃可能@

Leetcode 12

1 <= num <= 3999，输入的 int 换成级数表示，然后对 4 和 9 的情况做一下处理，可以吗？

Pasted image 20250428213451.png

这个题目好像已经把程序给出来了。 Pasted image 20250428214025.png

那就先看是不是 4 或者 9，然后判断是哪一种，然后剪掉，然后

class Solution:
    def intToRoman(self, num: int) -> str:
	   first_int = num % 10
	   if first_int == 4:
		   pass
	   elif first_int == 9:
		   pass
	   else:

写到这觉得好像写成级数更好处理，因为判断减法要写太多 if 了。

class Solution:
	def expandToSeries(self, num: int) -> list:
		# Assume we have a * 1000 + b * 100 + c * 10 + d * 1
		a = num % 1000
		b = (num - a * 1000) % 100
		c = ...
    def intToRoman(self, num: int) -> str:

太蠢了

直接转换成字符串。可以用列表推导式，此外，为什么不用一个table？

列表表达式 [expression for item in iterable if condition]

class Solution:
	def intToRoman(self, num: int) -> str:
		thousands = ["", "M", "MM", "MMM"] 
		hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"] 
		tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"] 
		ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
		num_list = [int(char) for char in str(num)]
		
		result = thousands[num_list[0]] + hundreds[num_list[1]] + tens[num_list[2]] + ones[num_list[3]]
		return result

太蠢了，这样不是假设一定有四位了吗

a = num // 1000
b = (num % 1000) // 100
c = (num % 100) // 10
d = num % 10

result = thousands[a] + hundreds[b] + tens[c] + ones[d]

AI：使用贪心算法

def int_to_roman_greedy(num: int) -> str:
    # 值和符号的映射，必须从大到小排列
    value_symbols = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"),
        (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"),
        (5, "V"), (4, "IV"), (1, "I")
    ]

    roman_numeral = []
    for value, symbol in value_symbols:
        while num >= value:
            roman_numeral.append(symbol)
            num -= value
        if num == 0: # 提前结束
            break
    return "".join(roman_numeral)

# 示例
print(f"1994 -> {int_to_roman_greedy(1994)}") # MCMXCIV
print(f"58 -> {int_to_roman_greedy(58)}")   # LVIII
print(f"3 -> {int_to_roman_greedy(3)}")     # III

Pasted image 20250428221907.png

通过

之后来学

Warning

55

如果在某一步的数比距离大，那么结束。

感觉正着走完全就是穷举了，没有什么简化办法。

不，好像有，如果紧接着的下一位位数不变，那么跳到下一位肯定没问题。

当前位数，步数，考虑的步数，如果，那么跳到这里没有问题。

对于有问题的情况下，跳，类推。

代码实现

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        position = 0
        j = 0
        if nums[position] == 0:
            return False
        while j <= nums[position]:
            if position + nums[position] < len(nums):
                return True
            elif nums[position + j] >= nums[position] - j:
                position = position + j
                j = 1
            else:
                j += 1

Pasted image 20250428231700.png

if position + nums[position] < len(nums): 这一句写反号了

提交： Pasted image 20250428231914.png
再次修改

Pasted image 20250428232120.png

Pasted image 20250428232125.png
看出你最后懒了，判断太草率了。好好想想什么时候截止：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True    
        position = 0
        j = 0
        if nums[position] == 0:
            return False
        while j <= nums[position]:
            if position + nums[position] >= len(nums) - 1:
                return True
            elif nums[position + j] >= nums[position] - j:
                position = position + j
                j = 1
            else:
                j += 1
        return position == n + 1

还捉了个虫 Pasted image 20250428232403.png

Pasted image 20250428232518.png Pasted image 20250428232520.png

AI 教学

class Solution: # 最终简洁版
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        max_reach = 0
        for i in range(n):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
            # 优化：如果已经可以覆盖终点，没必要继续遍历
            # if max_reach >= n - 1:
            #     return True
        # 如果循环正常结束，说明最后一个位置 n-1 也是可达的 (i <= max_reach)
        return True

哎，薄纱。